//字符串分割: https://www.nowcoder.com/practice/5f3b7bf611764c8ba7868f3ed40d6b2c?tpId=46&tqId=29041&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& dict) {
        if (s.empty()) 
        {
            return false;
        }
        if (dict.empty()) 
        {
            return false;   
        }
        vector<bool> can_break(s.size() + 1, false);
        // 初始化F(0) = true
        can_break[0] = true;
        for (int i = 1; i <= s.size(); i++) 
        {
               for (int j = i - 1; j >= 0; j--) 
               {
                // F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR
                // false 第j+1个字符的索引为j
                if (can_break[j] &&
                    dict.find(s.substr(j, i - j)) != dict.end()) 
                {
                    can_break[i] = true break;
                }
            }
        }
        return can_break[s.size()];
    }
};